package com.coder.algorithm.leetcode

import kotlin.math.min

/**
 * [209. 长度最小的子数组](https://leetcode-cn.com/problems/minimum-size-subarray-sum/)
 * 方法一：暴力破解
 * 方法二：确定sums数组，遍历sums，并二分找到另一个下标
 * 方法三：滑动窗口
 *
 * @author yuhus
 * @date: 2022/3/29
 */
object l_0209 {
    /**
     * 滑动窗口，start和end为窗口的开始位置和结束位置
     * 关键在于滑动窗口
     */
    fun minSubArrayLen(target: Int, nums: IntArray): Int {
        var minLen = nums.size + 1
        var start = 0
        var end = 0
        var sum = 0
        while (end < nums.size) {
            sum += nums[end]
            while (sum >= target) {
                if (minLen > end - start + 1) {
                    minLen = end - start + 1
                }
                sum -= nums[start]
                start++
            }
            end++
        }
        if (minLen == nums.size + 1) {
            minLen = 0
        }
        return minLen
    }
}